#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <iostream>

namespace part1
{

    using Position = std::pair<int, int>; 

    std::vector<std::string> readImage();
    void expandImage(std::vector<std::string>& image);
    std::vector<Position> getGalaxiesPosition(const std::vector<std::string>& image);
    int calculateShortestPath(const std::vector<Position>& galaxies);

    void solute()
    {
        auto printImage = [] (const std::vector<std::string>& image) {
            for (const std::string& line : image)
                std::cout << line << std::endl;
        };

        std::vector<std::string> image {readImage()};
        expandImage(image);
        std::vector<Position> galaxies {getGalaxiesPosition(image)};
        std::cout << calculateShortestPath(galaxies) << std::endl;
    }

    std::vector<std::string> readImage()
    {
        std::ifstream infile {"./src/day11/input.txt"};
        std::string line {};
        std::vector<std::string> image {};
        while (std::getline(infile, line))
            image.emplace_back(std::move(line));
        return image;
    }

    void expandImage(std::vector<std::string>& image)
    {
        // Column expand
        std::size_t row {image.size()};
        std::size_t column {image.front().size()};

        // Column
        std::vector<std::size_t> insertCols {};
        for (std::size_t c = 0; c < column; ++c)
        {
            bool allEmpty {true};
            for (std::size_t r = 0; r < row; ++r)
            {
                if (image[r][c] != '.')
                {
                    allEmpty = false;
                    break;
                }
            }
            
            if (allEmpty) insertCols.emplace_back(c);
        }

        for (std::size_t i = 0; i < insertCols.size(); ++i)
        {
            for (std::size_t r = 0; r < row; ++r)
                image[r].insert(insertCols[i] + i, 1, '.');
        }

        // Row
        column = image.front().size();
        std::string emptyLine (column, '.');

        std::vector<std::size_t> insertRows {};
        for (std::size_t r = 0; r < row; ++r)
        {
            if ( emptyLine == image[r])
                insertRows.emplace_back(r);
        }

        for (std::size_t i = 0; i < insertRows.size(); ++i)
        {
            std::size_t j {i + insertRows[i]};
            auto iter {image.begin()};
            while (j-- != 0) iter++;
            image.insert(iter, emptyLine);
        }
    }

    std::vector<Position> getGalaxiesPosition(const std::vector<std::string>& image)
    {
        std::size_t row {image.size()};
        std::size_t column {image.front().size()};
        std::vector<Position> positions {};

        for (std::size_t r = 0; r < row; ++r)
        {
            for (std::size_t c = 0; c < column; ++c)
            {
                if (image[r][c] == '#')
                    // Never overflow!
                    positions.emplace_back(static_cast<int>(r), static_cast<int>(c));
            }
        }
        return positions;
    }

    int calculateShortestPath(const std::vector<Position>& galaxies)
    {
        std::size_t galaxiesSize {galaxies.size()};
        std::vector<int> paths {};
        int pathSum {0};

        auto absInt = [] (int v) -> int {
            return v > 0 ? v : -v;
        };
        auto getPath = [&absInt] (const Position& startPos, const Position& endPos) -> int {
            int absX {absInt(startPos.first - endPos.first)};
            int absY {absInt(startPos.second - endPos.second)};
            return absX + absY;
        };

        for (std::size_t s = 0; s < galaxiesSize; ++s)
        {
            for (std::size_t e = 0; e < s; ++e)
            {
                int path {getPath(galaxies[s], galaxies[e])};
                paths.emplace_back(path);
                pathSum += path;
            }
        }

        return pathSum;
    }

}